package com.my.tree;

import java.util.ArrayList;
import java.util.List;

public class WidthTraversal {
	
	private static class Node {
		private String name;
		private Node left;
		private Node right;

		public Node(String name) {
			super();
			this.name = name;
		}

		public Node(String name, Node left, Node right) {
			super();
			this.name = name;
			this.left = left;
			this.right = right;
		}
		
		public String toString() {
			return name;
		}
	}
	
	/**
	 * Width traversal:
	 *    1
	 *  2   3
	 * 4 5 6 7
	 * @param root
	 * @return Tree depth
	 */
	public static void widthTraverse(Node root) {
		List<Node> buf = new ArrayList<>();
		if (root.left == null && root.right == null) {
			return;
		}
		buf.add(root);
		// Pop head, if head.left is NOT null, add to queue, if head.right is
		// NOT null, add to queue
		while (!buf.isEmpty()) {
			Node tmp1 = buf.remove(0);
			System.out.print(tmp1 + " ");
			if(tmp1.left != null || tmp1.right != null)
			if (tmp1.left != null) {
				buf.add(tmp1.left);
			}
			if (tmp1.right != null) {
				buf.add(tmp1.right);
			}
		}
		return;
	}
	
	public static int detectTreeDepth(Node root) {
		if(root == null) return 0;
		if(root.left == null && root.right == null)
			return 1;
		Node l = root.left;
		Node r = root.right;
		int lDepth=0;
		int rDepth = 0;
		if(l != null) {
			lDepth = detectTreeDepth(l);
		}
		if(r != null) {
			rDepth = detectTreeDepth(r);
		}
		if(lDepth >= rDepth) return ++lDepth;
		else return ++rDepth;
	}
	
	public static void printTree(Node root) {
		
	}
	
	public static void reverseTree(Node root) {
		//Reverse here:
		printTree(root);
	}

	/**
	 * @param args
	 *
	 **/
	public static void main(String[] args) {
		Node node7 = new Node("7");
		Node node6 = new Node("6");
		Node node5 = new Node("5");
		Node node4 = new Node("4");
		
		Node node3 = new Node("3", node6, null);
		Node node2 = new Node("2", null, node5);
		
		Node node1 = new Node("1", node2, node3);
		
		System.out.println("Tree depth: " + detectTreeDepth(node1));
	}

}
